#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int tmp[50010];
    int mergesort1(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int ans = 0;
        ans += mergesort1(nums, l, mid);
        ans += mergesort1(nums, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            else
            {
                ans += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= r)
            tmp[i++] = nums[cur2++];
        for (i = l; i <= r; ++i)
            nums[i] = tmp[i - l];
        return ans;
    }
    int reversePairs(vector<int>& record) {
        return mergesort1(record, 0, record.size() - 1);
    }

    int tmp1[100001];
    int tmp2[100001];
    vector<int> ans;
    void mergesort(vector<int>& nums, vector<int>& index, int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) >> 1;
        mergesort(nums, index, l, mid);
        mergesort(nums, index, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmp1[i] = nums[cur2];
                tmp2[i++] = index[cur2++];
            }
            else
            {
                ans[index[cur1]] += r - cur2 + 1;
                tmp1[i] = nums[cur1];
                tmp2[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid)
        {
            tmp1[i] = nums[cur1];
            tmp2[i++] = index[cur1++];
        }
        while (cur2 <= r)
        {
            tmp1[i] = nums[cur2];
            tmp2[i++] = index[cur2++];
        }
        for (i = l; i <= r; ++i)
        {
            nums[i] = tmp1[i - l];
            index[i] = tmp2[i - l];
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ans.resize(n);
        vector<int> index(n);
        for (int i = 0; i < n; ++i)
            index[i] = i;
        mergesort(nums, index, 0, n - 1);
        return ans;
    }

    int tmp[50001];
    int mergesort2(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int cur1 = l, cur2 = mid + 1, i = 0, ans = 0;
        ans += mergesort2(nums, l, mid);
        ans += mergesort2(nums, mid + 1, r);
        while (cur2 <= r)
        {
            while (cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) ++cur1;
            if (cur1 > mid) break;
            ans += mid - cur1 + 1;
            ++cur2;
        }
        cur1 = l, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            else
                tmp[i++] = nums[cur2++];
        }
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= r)
            tmp[i++] = nums[cur2++];
        for (i = l; i <= r; ++i)
            nums[i] = tmp[i - l];
        return ans;
    }
    int reversePairs(vector<int>& nums) {
        return mergesort2(nums, 0, nums.size() - 1);
    }

    bool rowcheck[9][10];
    bool colcheck[9][10];
    bool subboard[3][3][10];
    vector<pair<int, int>> spaces;
    bool dfs(vector<vector<char>>& board, int pos)
    {
        if (pos == spaces.size()) return true;
        auto kv = spaces[pos];
        for (char digit = '1'; digit <= '9'; ++digit)
        {
            int index = digit - '0';
            if (!rowcheck[kv.first][index] && !colcheck[kv.second][index] && !subboard[kv.first][kv.second][index])
            {
                board[kv.first][kv.second] = digit;
                rowcheck[kv.first][index] = colcheck[kv.second][index] = subboard[kv.first / 3][kv.second / 3][index] = true;
                if (dfs(board, pos + 1)) return true;
                board[kv.first][kv.second] = '.';
                rowcheck[kv.first][index] = colcheck[kv.second][index] = subboard[kv.first / 3][kv.second / 3][index] = false;
            }
        }
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.') spaces.emplace_back(i, j);
                else
                {
                    int digit = board[i][j] - '0';
                    rowcheck[i][digit] = colcheck[j][digit] = subboard[i / 3][j / 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
    }
};